/**
 * @file     commonChars.ts
 * @brief    [1002. 查找共用字符](https://leetcode.cn/problems/find-common-characters/description/)
 * @author   Zhu
 * @date     2023-02-14 01:03
 */

/**
 * 通用解法
 */
function commonChars(words: string[]): string[] {
    interface Dictionary {
        [key: string]: number;
    }

    const INVALID_VALUE = -1;

    function getDict(letters: string) {
        const dict: Dictionary = {};
        for (const letter of letters) {
            dict[letter] = (dict[letter] ?? 0) + 1;
        }
        return dict;
    }

    function arrayFromDict(dict: Dictionary = {}) {
        const result: string[] = [];
        for (const letter in globalDict) {
            for (let i = 0; i < globalDict[letter]; i++) {
                result.push(letter);
            }
        }
        return result;
    }

    let globalDict: Dictionary | undefined;
    for (const word of words) {
        // init the first dict as the global one
        if (!globalDict) {
            globalDict = getDict(word);
            continue;
        }
        const localDict: Dictionary = {};
        // reserve the local dictionary's valid letter counts
        for (const letter of word) {
            if (!globalDict[letter]) continue;
            const localLetter = localDict[letter] ?? 0;
            if (localLetter >= globalDict[letter]) {
                localDict[letter] = INVALID_VALUE;
            } else {
                localDict[letter] = localLetter + 1;
            }
        }

        // replace with the smaller letter counts
        for (const letter in globalDict) {
            if (!localDict[letter]) {
                delete globalDict[letter];
            } else if (localDict[letter] !== INVALID_VALUE) {
                globalDict[letter] = localDict[letter];
            }
        }
    }

    return arrayFromDict(globalDict);
}

/**
 * 26字母数组表
 */
function commonChars(words: string[]): string[] {
    const minFreq = new Array(26).fill(Infinity);

    for (const word of words) {
        const freq = new Array(26).fill(0);
        for (const letter of word) {
            freq[letter.charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
        }

        for (let i = 0; i < 26; i++) {
            minFreq[i] = Math.min(minFreq[i], freq[i]);
        }
    }

    const result: string[] = [];
    for (let i = 0; i < 26; i++) {
        for (let j = 0; j < minFreq[i]; j++) {
            result.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
        }
    }
    return result;
}
